//BF与KMP 的研究
public class TestDemo1 {
    /**
     * @param str  主串
     * @param sub  子串
     * @return  找到子串在主串中的位置
     */
    public static int KMP(String str,String sub) {
        int lenstr = str.length();
        int lensub = sub.length();
        int i = 0;    //遍历主串
        int j = 0;  //遍历子串
        if(str == null || sub == null) return -1;
        if(lenstr == 0 || lensub == 0) return -1;
        if(lensub == 1) {
            while(i<lenstr && j<lensub) {
                if(str.charAt(i) == sub.charAt(j)) {
                    i++;
                    j++;
                } else {
                    i++;
                    j = 0;
                }
            }
        } else {
            int[] next = new int[lensub];
            getNext(sub,next);
            while(i<lenstr && j<lensub) {
                //这里j==-1也能进，是因为第一个都不相同的时候，i++就往后走，j++还是等于0，相当于还在0下标
                if( j == -1 ||str.charAt(i) == sub.charAt(j)) {
                    i++;
                    j++;
                } else {
                    j = next[j];
                }
            }
        }
        if(j >= lensub) {        //如果j遍历完，说明找到了子串；
            return i-j;
        } else {                 //如果i遍历完，说明主串没找到子串；
            return -1;
        }
    }
    public static void getNext(String sub,int[] next) {
            next[0] = -1;
            next[1] = 0;
            int i = 2;    //表示当前所求next数组的下标
            int k = 0;    //表示i前一项所需要退回的值
            while(i < sub.length()) {
                if(k == -1 || sub.charAt(i-1) == sub.charAt(k)) {   //当k == -1时 ，表示next[0]到j-1没找到符合真子串；
                    next[i] = k+1;   //所以next[i] = -1+1 = 0;
                    k++;             //所以下一个i前面的k=0，需要退回到0下标
                    i++;
                } else {
                    k = next[k];
                }
            }
    }
    public static int BF2(String str,String sub) {   //BF小小优化
        int lenstr = str.length();
        int lensub = sub.length();
        int i = 0;
        int j = 0;
        if(str == null || sub == null) return -1;
        if(lenstr == 0 || lensub == 0) return -1;
        while(i<lenstr && j<lensub) {
            if(str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
            } else {
                int k = i-j+1;
                for (k = i-j+1; k < lensub; k++) {                    //从走过的数中查找与子串第一个相同的，i退到这然后从这继续开始走
                    if(str.charAt(k) != sub.charAt(0)) {
                        continue;
                    } else {
                        return k;
                    }
                }
                i = k;
                j = 0;
            }
        }
        if(j >= lensub) {        //如果j遍历完，说明找到了子串；
            return i-j;
        } else {                 //如果i遍历完，说明主串没找到子串；
            return -1;
        }
    }
    public static int BF(String str,String sub) {
        if(str == null || sub == null) {
            return -1;
        }
        int lenstr = str.length();
        int lensub = sub.length();
        int i = 0;
        int j = 0;
        if(lenstr == 0 || lensub == 0) {
            return -1;
        }
        while(i<lenstr && j<lensub) {
            if(str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
            } else {
                i = i-j+1;
                j = 0;
            }
        }
        if(j >= lensub) {        //如果j遍历完，说明找到了子串；
            return i-j;
        } else {                 //如果i遍历完，说明主串没找到子串；
            return -1;
        }
    }
    public static void main(String[] args) {
        String str = "abcabcabd";
        String sub = "abd";
        int ret = KMP(str,sub);
        System.out.println(ret);
    }
}
